package jjn.round1;

/**
 * @author Jjn
 * @since 2022/11/12 11:26
 */
public class LeetCode494_TargetSum {
    private int count;

    public int findTargetSumWays(int[] nums, int target) {
        this.count = 0;
        backtrack(nums, target, 0, 0);
        return count;
    }

    private void backtrack(int[] nums, int target, int sum, int index) {
        if (index >= nums.length) {
            if (sum == target) {
                count++;
            }
            return;
        }
        backtrack(nums, target, sum + nums[index], index + 1);
        backtrack(nums, target, sum - nums[index], index + 1);
    }
}
